perm filename HSTHST.PRO[DLN,MRC]8 blob
sn#346414 filedate 1978-04-02 generic text, type C, neo UTF8
COMMENT ā VALID 00016 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00003 00002 Dialnet memo #2
C00005 00003 CONVENTIONS USED IN THIS DOCUMENT
C00007 00004 PREFACE
C00010 00005 INTRODUCTION
C00015 00006 GOALS
C00018 00007 LINE TRANSMISSION PROTOCOL
C00025 00008 CHECKSUM ALGORITHM
C00027 00009 ALLOCATION ISSUES
C00032 00010 PACKET FORMAT
C00035 00011 HOST-HOST PROTOCOL OP-CODES
C00039 00012 OP CODES (continued)
C00042 00013 GLOSSARY
C00047 00014 GLOSSARY (continued)
C00052 00015 GLOSSARY (continued)
C00053 00016 REFERENCES
C00055 ENDMK
Cā;
Dialnet memo #2
SAILON silver girl
Dialnet Protocols
(or, the Protocols of DIAL)
Line Transmission and Host-Host Protocols
Mark Crispin
4/2/78
These protocols are being developed as part of the Dialnet project at the
Stanford University Artificial Intelligence Laboratory supported by NSF grant
MCS 77-02080 with John McCarthy as Principal Investigator. The project is
described in a paper available online at ARPAnet host SU-AI as
DIALNE.MEM[DLN,MRC] (Dialnet Memo #1).
This is HSTHST.PRO[DLN,MRC] at ARPAnet host SU-AI (octal 13, decimal 11.).
CONVENTIONS USED IN THIS DOCUMENT
All numbers without an explicit base (ie, octal or decimal) specified
should be interpreted as octal unless the number is immediately followed by a
dot, in which case it is decimal. However, numbers with intervening spaces
every three digits should be treated as binary (the intervening spaces are used
to facilitate conversion to octal).
All three-digit octal numbers should be interpreted as representing an
8.-bit byte, with bits right-justified within the number (ie, from 000 to 377).
Bytes are expressed in the form as returned by the modem (ie, lsb first); ie,
105 is transmitted in the bit stream as 101 000 10.
All six-digit octal numbers should be interpreted as representing a 16.-bit
double-byte, with bits right-justified within the number (ie, from 000000 to
177777). Double-bytes are expressed in the form returned by the modem (ie, low
order byte and lsb first); ie, 010041 is transmitted as 100 001 000 000 100 0.
PREFACE
"Aren't you glad you use Dialnet? Don't you wish everybody did?"
This document specifies a protocol for use in communication between Host
computers using the Dialnet protocols. In particular, it describes the protocol
used to ensure error-free data communication between two independent processes
on two different (and possibly incompatible) systems.
In actuality, this document describes TWO protocols: the line transmission
protocol and the host-host protocol. The former handles packet framing and line
error detection, the latter the protocol for two processes on dissimilar systems
to communicate. However, unlike other communications protocols, in Dialnet the
distinction is not as clear. Additionally, it is highly likely that both will
be implemented within the same process.
Another closely related protocol is the the initial connection protocol,
described elsewhere in a separate document. This is because an ICP is generally
implemented as part of a tertiary process.
In the rest of this document, the term "host-host protocol" will be used to
refer to the combined line transmission and host-host protocol.
Questions concerning Dialnet protocols should be addressed to:
Mark Crispin
Artificial Intelligence Laboratory
Stanford, California 94305
(415) 491-4712
MRC@SU-AI
Copies of all Dialnet-related correspondence should be sent to John
McCarthy (Dialnet principal investigator) and Les Earnest at the above US mail
address or via ARPAnet mail to JMC@SU-AI and LES@SU-AI.
It is the author's intent that these protocols are both simple in their
implementation and powerful in their operation. Certainly a major design
consideration was to design protocols that ordinary mortals could implement on
their systems.
INTRODUCTION
Dialnet provides a capability for geographically separated computers,
called hosts, to communicate with each other. The host computers typically
differ from one another in type, speed, word length, operating system, etc.
Each computer utilizes Dialnet via the ordinary phone lines and special modems.
However, just having compatible modems is insufficient for communication
between processes running in two dissimilar hosts. The processes must have some
agreement as to the method of initiating communication, the interpretation of
transmitted data, data flow, error detection etc. While it is possible for
individual pairs of hosts or processes interested in communication with each
other to establish private protocols, it is more desirable for a Dialnet-wide
set of standard protocols to be established to minimize the amount of
implementation effort involved in Dialnet-wide communication.
Hence, a "layered" approach to communications protocols similar to those of
the ARPAnet are specified here. The primary layer is the protocol of the
dial-up modems. The secondary protocol is the host-host protocol described here
and the initial connection protocol. The tertiary protocols, described
elsewhere, include: (in approximate order of importance)
FTP - File transfer protocol for reading, writing, and
manipulating files at a remote host.
MAIL - Sending and receiving letters between different users at
different hosts. These "letters" tend to be things like
memos or such which are read by the user at his/her
convenience instead of immediately.
SEND - Sending and receiving short letters with immediate delivery
and output on the user's console.
LINK - Teleconferencing between two or more users with character at
a time immediate delivery of user type-in.
INFO - A general service providing information at the host,
including access information, currently logged-in users, how
not-logged-in users may be contacted, etc.
TELNET - Mapping of an arbitrary console keyboard/printer at the
local host to a Dialnet virtual terminal which communicates
with a terminal server process at the remote host. The
remote host's server process maps the virtual terminal's
protocol into the host's own local terminal's protocol. In
this manner, users of one host can connect to another and
log in, etc. as if they were at a local console at the
remote host. There are probably going to be several levels
of TELNET; the first and simplest will be a simple
"connection" like a phone connection with no options.
Others, such as ARPAnet-compatible TELNET (ARPATLNT),
display SUPDUP (SUPDUP), and other forms of remote terminal
access will be provided.
GOALS
1. An essentially error-free data link. By this I mean no undetected errors,
no missed data, and error correction which is invisible to the user process.
2. Simple enough to put into small systems yet powerful enough to handle
sophisticated data communications.
3. Optimal for mailing and other message communication purposes, then for file
transfer, then for telnetting. Dialnet is intended primarily for
communications between two hosts where the physical amount of data
transmitted and the actual connect time is relatively short.
4. Efficient data communication with no deadlock situations.
5. Allow for upwards-compatible extensions in future incantations of Dialnet.
7. Allow for private protocols to be established.
NON-GOALS
1. The comprehensive features of the ARPAnet or other high-bandwidth networks.
Dialnet will provide the same USER services as a network such as the
ARPAnet; but it is important to realize that Dialnet is a low-bandwidth
communication protocol and not a physical network such as the ARPAnet.
2. Low-level handling of byte sizes of other than 8.-bit bytes.
3. Variable-format packets. It makes everything simpler to use fixed format.
4. Encryption or data compression at the host-host level. This belongs in the
higher-level protocols.
5. Use of non-ASCII character sets at the host-host level.
LINE TRANSMISSION PROTOCOL
All data is sent in the form of packets, which contain a packet header,
some data, and a packet trailer. The packet header serves to identify the type
of packet (ie, its functionality) and the size of the data area. The packet
trailer provides a checksum for the packet.
All packets have are in the same format, illustrated on the PACKET FORMAT
page. The begin with a start of packet frame, followed by a packet header, an
optional data area, a packet checksum, and an end of packet frame. The reason
for this was to make implementation as simple as possible and to provide a
clear, unambigious format for packets. Using this scheme it is possible for the
same read-packet routine to read all types of input packets.
Both the packet header and the packet trailer begin with fixed values.
These are used in packet framing. The bytes which indicate start of packet are
called SOP, and consist of ASCII DLE (220) followed by STX (202); similarly, the
bytes which indicate end of packet are called EOP, and are ASCII DLE followed by
ETX (203). Note that the 200 bit is on in DLE, STX, and ETX. If a 220 byte is
to be sent, it is quoted by being sent twice. DLE followed by anything other
than STX, ETX, or DLE is currently undefined; any such combination when received
should be discarded. Note that 020, 002, and 003 are not considered to be DLE,
STX, and ETX.
All packets have a packet number, which starts at 000 and is incremented
with each packet sent. The packet number wraps around to 000 from 377. Up to
6. (the default window size) packets may be sent before an acknowledgement is
received for (at least) the first packet. The window begins with the first
unacknowledged packet; therefore the window size is an allocation which is used
up as packets are sent and is given back as packets are acknowledged. RST is an
exception; since it totally initializes a connection it may be sent despite a
full window, additionally, its packet sequence number may be meaningless.
If the sender intends to temporarily "go idle", it should send a NOP,
repeated at least every 5. seconds. This assures the receiver that the sender
is still up. If the sender has gone idle because of an acknowledgement wait, it
should repeat the last packet of the window instead of sending a NOP.
A properly received packet (ie, with proper framing and correct checksum)
must be acknowledged for the sender to know that the receiver successfully
received the packet and to release that packet from the window. Each packet has
an acknowledgement byte which is used for this purpose. This byte in a packet
sent by the receiver contains the number of the highest successfully received
packet. Acknowledging a packet implies acknowledging all unacknowledged packets
with lower packet numbers, therefore a successfully received packet can merely
set the acknowledgement byte for the next packet to be sent without actually
forcing a packet to be sent.
Packets must be received in sequence, with the exception of RST packets
(see above). If the receiver receives a packet it has already acknowledged it
should discard it. Packets which have a sequence number higher than the
expected packet and packets with incorrect checksum should be discarded, and an
ERR sent for the expected packet. In the event of a framing error, the receiver
should discard all input until an SOP is encountered in the input stream. If a
packet is discarded for being out of sequence, its acknowledgement byte should
still be used, otherwise an acknowledgement may be unnecessarily missed.
There are no official timeouts for deciding whether a host is still alive
or whether the phone connection is poor enough to be unusable. Each implementor
must decide these for him/herself.
CHECKSUM ALGORITHM
The packet checksum algorithm used is the result of a conversation with
Knuth. The checksum is 16. bits long and all of the packet header variables and
the entire data area. It does NOT include the packet trailer or the SOP/EOP
packet framing codes. Note that framing checks happen even before the checksum
check, so the checksum is only needed for the more subtle byte corruption which
does not disturb packet framing.
The algorithm is: (all numbers should be read as octal)
checksum := 1;
while newchar do checksum := (checksum * 013215 + newchar) & 177777;
In PDP-10 assembly code, this is:
; CHKBYT adds a byte to the checksum in SUM. At the beginning of each packet
; SUM must be initialized to 1.
; Call: MOVE BYTE,<byte from data stream>
; PUSHJ P,CHKBYT
; <return>
CHKBYT: IMULI SUM,013215
ADDI SUM,(BYTE)
ANDI SUM,177777
POPJ P,
ALLOCATION ISSUES
An important concern which the DCP must handle is the problem of buffering
and allocation. The DCP must decide upon a maximum number of bytes of tertiary
data (ie, the data part of an MSG packet) which may be sent before the
connection becomes "frozen", waiting for a further allocation, and (at a lower
level) a maximum number of unacknowleged packets which may be received before
the connection freezes, waiting for at least one of these packets to be
acknowledged. The first is called the "allocation", the second the "window
size". The only way to break an allocation/acknowledgement wait other than
satisfying the wait is to send a RST to totally clear the connection.
The purpose of allocation is to allow hosts with limited buffering
capability to use the Dialnet facilities without having data overruns and the
resulting loss of efficiency in retransmitted packets. Note that allocation
does not affect retransmission, packet headers or trailers, or the data area of
any packets other than MSG packets. A host must be prepared to accept and
process non-MSG packets at any time.
This only covers tertiary data. The DCP normally should run at a high
enough priority to be able to handle all non-MSG packets coming in. If it
cannot, it still can win (sort of) by failing to acknowledge a packet which it
lost; eventually it will have to be retransmitted. It should be noted that this
is rather inefficient and it is best for the DCP to be a low-level process that
is guaranteed to be able to process non-MSG packets without buffering.
The window size is used in the line transmission protocol to prevent too
many packets being sent after an error to minimize retransmission time. The
setting of the window size is as critical as the allocation. In particular,
setting the window too small will cause unnecessary delays as the connection
becomes temporarily deadlocked waiting for acknowledgements which in turn might
be blocked due to an overly-small window. Eventually, an out-of-sequence
condition will cause an ERR and consequent clearing of the window, but some
delay will result. A window size that is too large may result in a large number
of packets being sent after a data error.
It is recommended that the window be large enough to accomodate the
allocation plus "room to spare". What the optimal allocation for a system is
depends upon its speed, storage capacity, reliability of the data link, and the
characteristics of the tertiary protocol in use. It is recommended that the
high-level process be given some choice in setting the allocations, as this last
factor is one of the most important. What is efficient for LINK or TELNET
purposes is not necessarily so for file transfer!
PACKET FORMAT
_________________________________________
| |
2 bytes | SOP marker |
| |
|=======================================|
| PACKET HEADER |
|=======================================|
| |
byte 1 | Channel number |
| |
|---------------------------------------|
| |
byte 2 | Op code |
| |
|---------------------------------------|
| |
byte 3 | Packet number |
| |
|---------------------------------------|
| |
byte 4 | Acknowledgement |
| |
|---------------------------------------|
| |
byte 5 | Data size (bytes) |
| |
|=======================================|
| PACKET DATA (optional) |
|=======================================|
| |
| |
| |
| |
byte 0 ā | Data (<size> bytes) |
<size-1> | |
| |
| |
| |
|=======================================|
| PACKET TRAILER |
|=======================================|
| |
byte 1 | Packet checksum (low) |
| |
|- - - - - - - - - - - - - - - - - - - -|
| |
byte 2 | Packet checksum (high) |
| |
|=======================================|
| |
2 bytes | EOP marker |
| |
|_______________________________________|
From this diagram, it can be seen that the minimum packet size is 11. bytes
and the maximum is 266. bytes. At 1200. baud, transmission timings range from
.092 second to 2.2 seconds.
HOST-HOST PROTOCOL OP-CODES
In the descriptions below, certain arguments are passed along with the
commands. These arguments are listed in the order in which they occur, along
with their byte size. They all occur in the DATA field of the packet.
CODE 000 NOP NO-OP
This command is a no-operation and should be ignored by the receiver except
that the packet still has to be acknowledged. It is used as an "idling" packet
to indicate that the sender is still alive but not transmitting anything. It is
also used to acknowledge a packet without doing anything else.
CODE 001 RPC REQUEST PROCESS CONNECTION
8. (Optional) Process ID of process to be connected to
2. (Optional) Initial allocation
1. (Optional) Initial window size
This is the basic establish connection command. It serves a dual purpose;
to request establishing a connection, and to confirm establishing a connection.
The process ID is optional. No restrictions on its use or non-use are imposed
by the host-host protocol. See the ICP protocol for process-ID conventions.
The initial allocation defaults to zero (ie, no MSG's may be sent until an ALL
is given). However, the initial window size defaults to 6. or the last size
set by WIN.
CODE 002 CLS CLOSE PROCESS CONNECTION
This is the basic terminate connection command. It may either terminate an
existing connection or abort a request for one.
CODE 003 ALL ALLOCATE
2. Bytes of allocation
This is the data allocation command. The receiver may send only up to the
specified number of data bytes in MSG packets before it must wait for a further
allocation. Allocation only applies to data in MSG packets; a host must be
ready to accept other packets at any time. Allocations are added to the current
allocation remaining.
CODE 004 WIN SET WINDOW SIZE
1. window size
This command sets the input window size; ie, it informs the receiver how
many packets it may send before waiting for an acknowledgement.
CODE 005 MSG MESSAGE
MSGSIZ Message passed to tertiary process
This is the basic data transmission command. The contents of the data part
are passed to the tertiary process. Data may be continuously sent until the
allocation runs out, after which no further MSG's may happen until another ALL
is given.
OP CODES (continued)
CODE 006 ERR ERROR
1. Packet sequence number to begin retransmission
1. Error condition code:
000 Packet error, retransmit
001 Packet violates protocol, you are losing
This is the command to tell the foreign host that it is losing with a
packet that it sent. The foreign host should examine the code and determine
what it is doing wrong.
CODE 007 RST RESET
Close all connections, abort all processes. This command may be sent by a
host which has just been restarted following a service interruption. It
instructs the other host to forget all packets, connections, etc. RST always
has packet number 000. RST's are acknowledged with a NOP that explicitly
acknowledges packet 000.
CODE 010 EOF END OF FILE
This op code is to cause an "end of file" condition to indicate the end of
data. This is necessary when dealing with binary data; for example, in the file
transfer protocol, there is no way otherwise to indicate the end of binary data
and the beginning of protocol commands.
CODE 011 INT INTERRUPT
This op code is provided to indicate an "interrupt" in the process. The
interpretation of "interrupt" is up to the processes using it. A sample use of
"interrupt" is in file transfer to indicate an aborted file transfer as opposed
to a normal end of file; in the case of an aborted file transfer the creation of
the copy of the file might be aborted instead of having that file closed, etc.
GLOSSARY
The following terms are used in this document and are defined here to
remove ambiguity:
ACKNOWLEDGEMENT -- an 8.-bit quantity which specifies the packet
sequence number of the highest consecutive packet which has
been successfully received. An acknowledgement implies that
all packets with lower sequence numbers have been received
as well.
ALLOCATION -- a 16.-bit quantity which specifies the number of
bytes that may be sent in MSG packets before a new
allocation. This is to provide for hosts with limited
buffering. Allocation applies only to the data part of MSG
packets and not to any other type of packet.
BYTE -- an 8.-bit quantity. While Dialnet transmissions are to
be considered as a bit stream, this concept is convenient to
use for many reasons.
BYTE SIZE -- this refers to the byte size of data as seen by the
host computer. All Dialnet transmissions should be
considered bit stream transmissions sent in units of 8.-bit
bytes.
CHANNEL -- an 8.-bit quantity identifying which data stream this
packet belongs to. Channels have no meaning to the
host-host protocol. See the ICP protocol for channel
conventions.
CHECKSUM -- a 16.-bit quantity containing a packet checksum, used
in error detection.
CONNECTION -- a logical connection between two processes.
Connections are bidirectional.
DATA -- an arbitrary amount of data which is either used as
arguments in the Host-Host protocol or as data to be passed
to a process utilizing Dialnet.
DATA COUNT -- a 8.-bit quantity indicating how many bytes are in
the data field of the packet. This quantity may be 000, in
which case there is no data field.
DIALNET -- a communications protocol for data transmission over
standard phone lines. This term also refers informally to
the set of hosts which implement Dialnet.
DIALNET CONTROL PROGRAM -- the process on each host responsible
for the host-host communications on that host. All the
other processes on that host send and receive their traffic
through the DCP.
EOP -- a marker used to indicate end of packet. EOP consists of
ASCII DLE (220) followed by ETX (202). It is a violation of
packet framing for a packet to end with anything other than
an EOP. A packet is not completely received until this code
has been received. Note that the 200 bit must be set for an
EOP to be recognized as such.
GLOSSARY (continued)
HOST -- a system with Dialnet-compatible modems and
Dialnet-support software which knows the telephone number of
at least one other host.
HOST-HOST PROTOCOL -- The protocol which provides for compatible
communication between two processes running on (probably)
dissimilar hosts.
LINE TRANSMISSION PROTOCOL -- The protocol which provides for
error free transmission between two hosts with a common
modem which use the Host-Host protocol.
OP CODE -- a Dialnet host-host protocol operation code.
PACKET -- a logical unit of data transmitted over a Dialnet link.
The packet is the elementary unit of Dialnet transmissions.
A packet is basically data with a header and trailer.
PACKET FRAMING -- a technique used in the line transmission
protocol which requires that all packets start with an SOP
marker and end with an EOP marker. A packet must be
properly framed for it to be considered to have been
received correctly. Framing errors cause the packet in
progress and all succeeding data to be discarded until
framing is restored.
PACKET ID -- an 8.-bit quantity which uniquely identifies a
packet at a given point in time. This is used to identify
packets if necessary in error recovery. Packet ID's may be
recycled after both hosts have agreed that the packet
associated with this packet ID has been correctly sent and
received. Packet numbers start with 000 when a phone
connection is made, are incremented with each new packet,
and wrap around to 000.
PROCESS -- an entity utilizing Dialnet. Dialnet traffic consists
of communications between processes.
PROCESS ID -- an ASCII string (currently 8. 8.-bit bytes) which
uniquely identifies the process. See the ICP and
higher-level protocols for process-ID conventions.
SERVER -- the initially passive process in a connection.
SOP -- a marker used to indicate start of packet. SOP consists
of ASCII DLE (220) followed by STX (203). It is a violation
of packet framing for a packet to begin with anything other
than an SOP. Any data received when an SOP is expected
should be discarded. Note that the 200 bit must be set for
an SOP to be recognized as such.
TIMEOUT -- A delay time for a specified action. If the desired
action does not occur within a specified time, a "timeout"
action is taken.
USER -- the initially active process in a connection.
GLOSSARY (continued)
WINDOW -- The margin for packets vs. their acknowledgements so
that ACK's do not have to be completely synchronous with
packets.
WINDOW SIZE -- The maximum number of unacknowledged packets which
may be pending at any time. This is similar to what the
ARPAnet calls "message allocation".
REFERENCES
The following documents describe communications protocols used in several
data communication networks and are listed here for reference:
ARPAnet: (The first packet-switched network)
[1] ARPAnet Protocol Handbook, 1978. Feinler and Postel (editors).
[2] Specifications for the Interconnection of a Host and an IMP, BBN
Report #1822, including the Interim Revision to Appendix F of BBN
Report 1822.
CHAOS: (MIT Artificial Intelligence Laboratory local network)
[1] A draft is available online at MIT-AI as MOON;CHAORD >. Moon.
DECnet: (Digital Equipment Corporation's communications protocols)
[1] Specification for: DDCMP (Digital Data Communications Message
Protocol). DEC.
[2] Specification for: NSP (Network Services Protocol). DEC.
[3] Specification for: DAP (Data Access Protocol). DEC.
LCS network: (MIT Laboratory for Computer Science local network)
[1] Local Network Notes.